package algorithms.roughgarden.part2.clustering;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.notion.algorithms.datastructures.UnionFind;

public class MainLarge {
	private static int noOfNodes;
	private static int noOfBitsPerNode;
	private static final String ONE="1";
	private static Map<BitSet, BitSetVertex> verticesMap;
	private static int maxSpacing;
	
	public static void main(String[] args) throws IOException {
		long init = System.currentTimeMillis();
		UnionFind<BitSetVertex> uf = new UnionFind<BitSetVertex>();
		InputStream is = Main.class.getResourceAsStream("clustering_big.txt");
		BufferedReader br = new BufferedReader(new InputStreamReader(is));
		String str;
		String[] strArr;
		str = br.readLine();
		strArr = str.split(" ");
		noOfNodes = Integer.parseInt(strArr[0]);
		noOfBitsPerNode = Integer.parseInt(strArr[1]);
		BitSet bs = null;
		BitSetVertex vertex;
		int vertexNumber = 0;
		verticesMap = new HashMap<BitSet, BitSetVertex>(noOfNodes);
		while((str=br.readLine())!=null){
			bs = new BitSet(noOfBitsPerNode);
			strArr = str.split(" ");
			for(int i=0;i<noOfBitsPerNode;i++){
				if(ONE.equals(strArr[i])){
					bs.set(i);
				}
			}
			vertex = new BitSetVertex(vertexNumber++, bs);
			//vertices.add(vertex);
			verticesMap.put(bs, vertex);
			
		}
		//all 0 distance nodes would have already been consumed
		maxSpacing = verticesMap.size();
		for(BitSetVertex v:verticesMap.values()){
			for(BitSet bitSetAtDIst:getListAtDistOneOrTwo(v.getBitSet())){
				vertex = verticesMap.get(bitSetAtDIst);
				if((null!=vertex) && (uf.find(v)!=uf.find(vertex))){
					maxSpacing--;
					uf.union(vertex, v);
					
				}
			}
		}
		System.out.println(maxSpacing);
		System.out.println(System.currentTimeMillis()-init);

	}
	
	private static final List<BitSet> getListAtDistOneOrTwo(BitSet sourceBitSet){
		List<BitSet> bitSetList = new ArrayList<BitSet>();
		BitSet clonedBitSet;
		for(int i=0;i<noOfBitsPerNode;i++){
			clonedBitSet = 	(BitSet)sourceBitSet.clone();
			clonedBitSet.flip(i);
			bitSetList.add(clonedBitSet);
		
		}
		for(int i=0; i<noOfBitsPerNode-1;i++){
			for(int j=i+1;j<noOfBitsPerNode;j++){
				clonedBitSet = 	(BitSet)sourceBitSet.clone();
				clonedBitSet.flip(i);
				clonedBitSet.flip(j);
				bitSetList.add(clonedBitSet);
			}
		}
		return bitSetList;
	}

}
